package leetcode.problems;

import java.util.Stack;

/**
 * _0415 Intersection of Two Linked Lists
 * 两个链表的交集
 * Created by gmwang on 2018/3/23
 */
public class _0415IntersectionofTwoLinkedLists {
    /**
     *  Write a program to find the node at which the intersection of two singly linked lists begins.
     For example, the following two linked lists:

     A:          a1 → a2
                         ↘
                         c1 → c2 → c3
                         ↗
     B:     b1 → b2 → b3
     begin to intersect at node c1.
     编写一个程序来查找两个单链表的交集的起始点。
     例如，下面的两个链表：
     开始在节点C1相交。
     注意：
         如果两个链表没有交集，返回null。
         链表在函数返回后必须保留原来的结构。
         您可以假设在整个链接结构中没有任何周期。
         您的代码最好在o（n）时间运行，只使用o（1）内存。
     */
    /**
     * 思路：
     * 1. 比较最大值，记录
     * 2. 比较最小值，记录
     * 3. 最大值 = max(最大值，当前-最小值)
     *
     * @param
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode node = null;
        Stack<ListNode> stack = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();
        if(headA ==null || headB == null) return node;
        while(headA != null || headA.next != null || headB != null || headB.next !=null){
                //判断是否是相同的因素，值和以后元素的值是否相等
                stack.push(headA);
                stackB.push(headB);
                if(stack.contains(headB)){
                    return headB;
                }else if( stackB.contains(headA)){
                    return headA;
                }else {
                    if(headA.next != null) headA = headA.next;
                    if(headB.next != null) headB = headB.next;
                }
        }
            return node;
    }
//    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        int lenA = length(headA), lenB = length(headB);
//        // move headA and headB to the same start point
//        while (lenA > lenB) {
//            headA = headA.next;
//            lenA--;
//        }
//        while (lenA < lenB) {
//            headB = headB.next;
//            lenB--;
//        }
//        // find the intersection until end
//        while (headA != headB) {
//            headA = headA.next;
//            headB = headB.next;
//        }
//        return headA;
//    }
//    private static int length(ListNode node) {
//        int length = 0;
//        while (node != null) {
//            node = node.next;
//            length++;
//        }
//        return length;
//    }
    public static void main(String[] args) {
        ListNode rootA1 = new ListNode(1);
        ListNode rootA2 = new ListNode(2);
        ListNode rootC1 = new ListNode(200);
        ListNode rootC2 = new ListNode(20);
        ListNode rootC3 = new ListNode(20);
        rootA1.next = rootA2;
        rootA2.next = rootC1;
        ListNode rootB1 = new ListNode(15);
//        ListNode rootB2 = new ListNode(7);
//        ListNode rootB3 = new ListNode(71);
        rootB1.next = rootC1;
//        rootB2.next = rootB3;
//        rootB3.next = rootC1;
        rootC1.next = rootC2;
        rootC2.next = rootC3;
        System.out.println(getIntersectionNode(rootA1,rootB1).val);
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}

